ToT (Tree of Thoughts, 사고의 나무, 2023-05-17)

1. 서론: 인공지능의 추론 패러다임 전환과 ToT의 등장

인공지능, 특히 거대 언어 모델(Large Language Models, 이하 LLM)의 발전은 지난 수년 동안 급격한 기술적 진보를 이룩했다. GPT-4, PaLM과 같은 모델들은 텍스트 생성, 번역, 요약 등 기본적인 자연어 처리 작업을 넘어 수학적 문제 해결, 코드 생성, 그리고 상식적 추론의 영역까지 능력을 확장해 왔다.1 그러나 이러한 눈부신 성과에도 불구하고, 현존하는 대부분의 LLM은 근본적인 구조적 한계에 직면해 있다. 그것은 바로 이 모델들이 기본적으로 ‘자기회귀적(autoregressive)’ 메커니즘에 의존한다는 점이다. 이 메커니즘은 텍스트를 생성할 때 왼쪽에서 오른쪽으로, 한 번에 하나의 토큰만을 순차적으로 결정한다.2 이러한 방식은 인간의 직관적이고 빠른 사고 과정, 즉 대니얼 카너먼(Daniel Kahneman)이 정의한 ‘시스템 1(System 1)’ 사고와 유사하다. 이는 신속하지만, 복잡한 계획이 필요하거나 초기 판단의 오류가 치명적인 결과를 초래하는 과제에서는 취약점을 드러낸다.4

기존의 ‘생각의 사슬(Chain of Thought, 이하 CoT)’ 프롬프팅 기법은 이러한 단발적 생성의 한계를 극복하기 위해 제안되었다. CoT는 모델이 최종 답변을 내놓기 전에 중간 추론 과정을 생성하도록 유도함으로써 복잡한 문제 해결 능력을 비약적으로 향상시켰다.1 하지만 CoT 역시 본질적으로 선형적인 사고의 흐름을 따른다는 점에서 한계를 가진다. 한 번 잘못된 추론의 고리가 형성되면, 모델은 그 오류를 수정하거나 되돌아갈(backtracking) 수단이 없이 오답을 향해 나아가게 된다.1 이는 마치 미로 찾기에서 한 번 선택한 길을 끝까지 가야만 하는 것과 같으며, 막다른 길에 다다랐을 때 이전 분기점으로 돌아와 다시 탐색하는 전략적 유연성이 결여되어 있다.

이러한 배경에서 등장한 ‘사고의 나무(Tree of Thoughts, 이하 ToT)’ 프레임워크는 LLM의 추론 방식을 근본적으로 재정의하는 시도이다. ToT는 문제를 해결하기 위한 중간 단계인 ’생각(thought)’을 명시적인 단위로 정의하고, 이를 바탕으로 다양한 가능성의 경로를 탐색하는 트리 구조를 형성한다.1 이는 인간의 ‘시스템 2(System 2)’ 사고, 즉 느리지만 논리적이고, 계획적이며, 의식적인 숙고 과정을 인공지능에 이식하려는 노력의 일환이다. 본 보고서는 ToT의 이론적 배경부터 구체적인 메커니즘, 실험적 검증 결과, 그리고 향후 인공지능 아키텍처에 미칠 영향까지 포괄적으로 분석한다. 특히 기존 문헌과 연구 자료를 바탕으로 ToT가 어떻게 LLM을 단순한 텍스트 생성기에서 진정한 의미의 ’문제 해결자(Problem Solver)’로 진화시키는지에 대해 심도 있게 논의한다.

graph TD

subgraph "System 2: ToT (Deliberate Search)"
S2_In["Input Query"] --> S2_Plan["Planning & Decomposition"]
S2_Plan --> S2_Exp["Explore Paths"]
S2_Exp --> S2_Eval["Self-Evaluation"]
S2_Eval --"Review"--> S2_Exp
S2_Eval --"Confirm"--> S2_Out["Final Solution"]
style S2_In fill:#e3f2fd,stroke:#1565c0
style S2_Out fill:#c8e6c9,stroke:#2e7d32
end

subgraph "System 1: Standard LLM (Autoregressive)"
S1_In["Input Query"] --> S1_T1["Token 1"]
S1_T1 --> S1_T2["Token 2"]
S1_T2 --> S1_T3["Token 3"]
S1_T3 --> S1_Out["Immediate Output"]
style S1_In fill:#f5f5f5,stroke:#333
style S1_Out fill:#ffcc80,stroke:#ef6c00
end

2. 이론적 배경 및 선행 연구 분석

ToT의 독창성을 이해하기 위해서는 먼저 LLM의 추론 능력을 강화하기 위해 시도되었던 기존 기법들의 발전 과정을 살펴보고, ToT가 이들과 어떻게 차별화되는지 이론적으로 정립할 필요가 있다.

2.1 기존 프롬프팅 전략의 진화와 한계

LLM의 활용 방식은 단순히 입력을 출력으로 매핑하는 것에서 시작하여, 점차 복잡한 중간 과정을 포함하는 방향으로 진화해 왔다.

IO 프롬프팅은 모델에게 질문을 던지고 바로 답을 요구하는 가장 기본적인 형태이다. 이는 간단한 사실 검색에는 유효하지만, 다단계 추론이 필요한 수학 문제나 논리 퀴즈에서는 처참한 성능을 보인다. CoT는 “단계별로 생각해 보자(Let’s think step by step)“와 같은 유도를 통해 모델이 중간 단계를 생성하게 함으로써 성능을 높였으나, 여전히 ‘탐욕적(Greedy)’ 디코딩 방식, 즉 매 순간 가장 그럴듯한 다음 토큰을 선택하는 방식에 머물러 있다.1

Self-Consistency는 CoT의 한계를 보완하기 위해 여러 개의 추론 경로를 생성하고 그중 가장 많이 도출된 답을 선택하는 방식이다.1 이는 “다양한 각도에서 문제를 바라보는” 효과를 주어 정확도를 높이지만, 근본적으로는 여러 개의 ‘시스템 1’ 사고를 모아놓은 것에 불과하다. 즉, 각 경로가 서로 독립적으로 생성되기 때문에, 하나의 경로에서 발견된 통찰이 다른 경로에 영향을 주거나, 가망 없는 경로를 조기에 파악하고 중단하는 효율적인 탐색이 불가능하다.5

graph TD

subgraph "Tree of Thoughts (ToT)"
ToT_Input["Input (x)"] --> ToT_Gen["Generate Thoughts"]
ToT_Gen --> ToT_Eval["Evaluate & Select"]
ToT_Eval --"Backtrack / Prune"--> ToT_Gen
ToT_Eval --"Proceed"--> ToT_Next["Next Thoughts"]
ToT_Next --> ToT_Output["Output (y)"]
style ToT_Input fill:#e1f5fe,stroke:#01579b,stroke-width:4px
end

subgraph "Self-Consistency (CoT-SC)"
SC_Input["Input (x)"] --> SC_Path1["Path 1 (CoT)"]
SC_Input --> SC_Path2["Path 2 (CoT)"]
SC_Input --> SC_Path3["Path 3 (CoT)"]
SC_Path1 --> SC_Vote["Majority Vote"]
SC_Path2 --> SC_Vote
SC_Path3 --> SC_Vote
SC_Vote --> SC_Output["Output (y)"]
style SC_Input fill:#f9f9f9,stroke:#333,stroke-width:2px
end

subgraph "Chain of Thought (CoT)"
CoT_Input["Input (x)"] --> CoT_z1["Think z1"]
CoT_z1 --> CoT_z2["Think z2"]
CoT_z2 --> CoT_Output["Output (y)"]
style CoT_Input fill:#f9f9f9,stroke:#333,stroke-width:2px
end

subgraph "Input-Output (IO)"
IO_Input["Input (x)"] --> IO_Output["Output (y)"]
style IO_Input fill:#f9f9f9,stroke:#333,stroke-width:2px
end

2.2 인지과학과 AI의 융합: 이중 정보 처리 이론의 적용

ToT는 인지 심리학의 **이중 정보 처리 이론(Dual Process Theory)**을 AI 모델 설계에 적극적으로 도입했다.4 인간의 뇌는 직관적이고 빠른 처리를 담당하는 시스템 1과, 복잡한 계산이나 계획 수립 시 활성화되는 시스템 2를 모두 사용한다. 기존의 LLM이 방대한 데이터를 학습하여 패턴을 매칭하는 시스템 1에 탁월하다면, ToT는 이 모델 위에 시스템 2의 기능을 덧입히는 구조이다.

ToT에서 LLM은 여전히 사고의 재료를 생성하는 역할을 수행하지만, 이 재료들을 어떻게 연결하고, 어떤 방향으로 나아갈지 결정하는 ‘제어(Control)’ 기능은 트리 탐색 알고리즘(BFS, DFS 등)이 담당한다. 이는 AI가 단순히 데이터를 앵무새처럼 흉내 내는 것을 넘어, 자신의 사고 과정을 **메타인지(Metacognition)**적으로 관찰하고 평가하는 단계로 진입했음을 시사한다.8 모델은 자신이 생성한 ’생각’이 문제 해결에 도움이 되는지 스스로 평가(Self-evaluation)하고, 그 결과에 따라 탐색의 방향을 수정한다.

graph TD
subgraph "Human Cognition (Dual Process Theory)"
H_Sys1["System 1: Fast, Intuitive"]
H_Sys2["System 2: Slow, Deliberate, Logical"]
end

subgraph "ToT Architecture"
AI_LLM["LLM (Token Generation)"]
AI_Search["Search Algorithm (BFS/DFS) + Evaluation"]
end

H_Sys1 --"Corresponds to"--> AI_LLM
H_Sys2 --"Corresponds to"--> AI_Search

AI_LLM --"Provides Raw Materials"--> AI_Search
AI_Search --"Control & Metacognition"--> AI_LLM

style AI_LLM fill:#fff3e0,stroke:#e65100
style AI_Search fill:#e8f5e9,stroke:#1b5e20

3. 사고의 나무(Tree of Thoughts) 프레임워크의 핵심 메커니즘

ToT는 단순한 프롬프트 엔지니어링 기법을 넘어, 문제 해결을 위한 알고리즘적 프레임워크로 이해해야 한다. ToT는 1) 사고의 분해(Decomposition), 2) 사고 생성기(Generator), 3) 상태 평가기(Evaluator), **4) 탐색 알고리즘(Search Algorithm)**이라는 네 가지 핵심 모듈로 구성된다.2

graph TD
Start["Start Problem Solving"] --> Decomposition["1: Thought Decomposition (Break down problem)"]

Decomposition --> Generator["1: Thought Generator (Generate Candidates)"]

subgraph "Generation Strategies"
Generator --> Sample["Sample (i.i.d): Creative Tasks"]
Generator --> Propose["Propose (Sequential): Logical Tasks"]
end

Sample --> Evaluator["1: State Evaluator (Heuristic Function)"]
Propose --> Evaluator

subgraph "Evaluation Methods"
Evaluator --> Value["Value (Score 1-10 or Classification)"]
Evaluator --> Vote["Vote (Select Best Promising State)"]
end

Value --> Search["1: Search Algorithm"]
Vote --> Search

subgraph "Search Strategies"
Search --> BFS["BFS (Breadth-First): Limit to top b states"]
Search --> DFS["DFS (Depth-First): Explore & Backtrack"]
end

BFS --> GoalCheck{"Goal Reached?"}
DFS --> GoalCheck

GoalCheck --"No (Pruning/Backtracking)"--> Generator
GoalCheck --"Yes"--> FinalOutput["Final Solution"]

3.1 사고의 분해 (Thought Decomposition)

복잡한 문제를 해결하기 위해서는 이를 다루기 쉬운 작은 단위로 쪼개야 한다. ToT에서는 이를 ’생각(Thought)’이라고 정의한다. 생각은 문제 해결을 위한 중간 단계로서, 일관성 있는 텍스트 시퀀스로 표현된다.1

• 단위의 중요성: 생각의 크기(granularity)는 매우 중요하다. 너무 작으면(예: 토큰 단위) 평가가 불가능하고, 너무 크면(예: 전체 문단) 생성 자체가 어려워진다.
• 적용 예시:
• 수학 문제 (Game of 24): 하나의 수식(예: “4 + 9 = 13”)이 하나의 생각이 된다.9
• 창의적 글쓰기: 글 전체를 쓰기 전의 ’개요’나 ‘플롯 계획’ 한 줄이 생각이 된다.10
• 여행 계획: 목적지 선정, 이동 수단 결정, 숙소 예약 등으로 단계를 나눈다.9

이러한 분해 과정은 모델이 한 번에 처리해야 할 인지적 부하를 줄여주고, 각 단계를 개별적으로 검증할 수 있게 해 준다.

graph TD
Problem["Complex Problem Solving"] --> Level1["Token Level"]
Problem --> Level2["Thought Level (ToT)"]
Problem --> Level3["Document Level"]

subgraph "Too Fine-Grained"
Level1 --> Issue1["Hard to Evaluate Meaning"]
Issue1 --> Result1["Inefficient Search"]
end

subgraph "Optimal Balance"
Level2 --> Benefit1["Manageable Unit"]
Benefit1 --> Benefit2["Easy to Evaluate"]
Benefit2 --> Result2["Effective Reasoning"]
end

subgraph "Too Coarse-Grained"
Level3 --> Issue2["Hard to Generate at once"]
Issue2 --> Result3["Low Success Rate"]
end

style Level2 fill:#fff59d,stroke:#fbc02d,stroke-width:2px
style Result2 fill:#81c784,stroke:#2e7d32

3.2 사고 생성기 (Thought Generator)

현재 상태(s)에서 다음 단계로 나아가기 위한 후보 생각(z)들을 생성하는 과정이다. ToT는 문제의 특성에 따라 두 가지 전략을 제시한다.9

1. 샘플링(Sample, i.i.d): 하나의 프롬프트를 여러 번 실행하여 독립적인 생각들을 얻는다 (z_1, z_2, \dots, z_k \sim p(z|s)). 이 방식은 창의적 글쓰기와 같이 정답 공간이 넓고 다양성이 중요한 과제에 적합하다.
2. 제안(Propose, sequential): “가능한 다음 단계들을 제안하라“는 식의 프롬프트를 사용하여, 모델이 한 번의 출력으로 여러 개의 대안을 나열하게 한다. 이는 24 게임이나 논리 퍼즐처럼 다음 단계가 제한적이고 명확한 규칙을 따르는 경우에 효율적이다. 예를 들어, “4, 9, 10, 13을 사용하여 만들 수 있는 다음 수식들을 나열하시오“라고 요청하는 것이다.

3.3 상태 평가기 (State Evaluator)

ToT의 가장 혁신적인 부분이자 성능의 핵심이다. 생성된 생각들이 최종 해결책에 도달할 가능성이 얼마나 되는지를 LLM이 스스로 판단하게 한다. 이는 강화학습에서의 가치 함수(Value Function) 역할을 LLM이 수행하는 셈이다.1

• 가치 평가(Value): 각 상태에 대해 수치적 점수(예: 1~10점)나 등급(확실함/가능성 있음/불가능함)을 부여한다.
• 예시 (24 게임): “남은 숫자가 이라면 24를 만들 수 있는가?” \rightarrow “불가능(Impossible)” 판정.10
• 예시 (수학): 목표 값과의 차이를 계산하여 점수화한다. 차이가 작을수록 높은 점수를 부여한다.4
• 투표(Vote): 여러 개의 후보 상태를 비교하여 가장 유망한 것을 선택한다. 정량적 평가가 어려운 창의적 영역에서 유용하다. “다음 중 어떤 플롯이 가장 흥미로운가?“와 같이 모델에게 투표를 요청한다.9

이 평가 과정은 탐색 트리에서 유망하지 않은 가지를 쳐내고(Pruning), 자원을 효율적으로 배분하는 나침반 역할을 한다.

3.4 탐색 알고리즘 (Search Algorithm)

생성되고 평가된 생각들의 구조(Tree)를 어떻게 탐색할 것인지 결정한다.1

• 너비 우선 탐색 (BFS - Breadth-First Search): 트리의 각 깊이(Depth)에서 가능한 모든 상태를 탐색한 뒤, 상위 b개의 유망한 상태만을 남기고 다음 깊이로 넘어간다. 24 게임이나 창의적 글쓰기처럼 단계 수가 고정되어 있거나 깊지 않은 문제에 적합하다.
• 깊이 우선 탐색 (DFS - Depth-First Search): 하나의 경로를 끝까지 탐색한 후, 결과가 만족스럽지 않으면 이전 분기점으로 돌아가(Backtracking) 다른 경로를 시도한다. 크로스워드 퍼즐처럼 제약 조건이 까다롭고, 막다른 길에 다다를 확률이 높은 문제에서 필수적이다.

4. 심층 사례 분석 및 실험 결과

ToT 논문과 후속 연구들은 세 가지 대표적인 과제를 통해 ToT의 성능을 검증했다. 이 과제들은 단순한 지식 검색이 아니라, 계획, 탐색, 그리고 제약 조건 충족을 요구한다는 공통점이 있다.

4.1 24 게임 (Game of 24): 수학적 계획 수립 능력의 검증

과제 개요: 4개의 숫자(예: 4, 9, 10, 13)를 사용하여 사칙연산(+, -, *, /)을 통해 24를 만드는 문제이다.

기존 방식의 실패: GPT-4에 CoT를 적용했을 때 성공률은 고작 **4%**에 불과했다.2 이는 모델이 “4 + 9 = 13“과 같이 초기에 그럴듯한 연산을 수행하지만, 남은 숫자들로 24를 만들 수 없게 되는 ’막다른 길’에 봉착했을 때 이를 복구하지 못하기 때문이다.

ToT 적용 과정:

1. 분해: 3단계의 수식으로 문제를 분해한다.
2. 생성 (Propose): 각 단계에서 가능한 연산 결과들을 제안한다.

• Input: 4, 9, 10, 13
• Thoughts: “4+9=13 (남은 숫자: 13, 10, 13)”, “13-9=4 (남은 숫자: 4, 4, 10)”,…

3. 평가 (Value): 각 상태에 대해 24 도달 가능성을 평가한다.

• Prompt: “Evaluate if the numbers can reach 24 (sure/likely/impossible)”.10
• Judgment: \rightarrow “10+14=24 sure”, \rightarrow “impossible”.

4. 탐색 (BFS): 너비 b=5로 설정하여, 매 단계에서 가장 유망한 5개의 수식 조합을 유지하며 탐색을 진행한다.14

결과: ToT는 **74%**의 성공률을 기록했다.2 이는 단순한 연산 능력의 차이가 아니라, ‘안 되는 경로를 미리 버리고 되는 경로를 찾아가는’ 탐색 능력의 유무가 결정적임을 보여준다.

graph TD
Input["Input: 4, 9, 10, 13"] --> Step1_Gen["Step 1: Generate Thoughts"]

Step1_Gen --> T1["Thought 1: 4+9=13 (Left: 10, 13, 13)"]
Step1_Gen --> T2["Thought 2: 10-4=6 (Left: 6, 9, 13)"]
Step1_Gen --> T3["Thought 3: ..."]

T1 --> Eval1["Evaluation: Sure/Likely/Impossible"]
T2 --> Eval2["Evaluation: Impossible"]

Eval1 --"Possible (Keep)"--> Step2_Gen["Step 2: Generate Next Thoughts"]
Eval2 --"Impossible (Prune)"--> Stop["Stop Branch"]

Step2_Gen --> T2_1["Thought: 13-10=3 (Left: 3, 13)"]
Step2_Gen --> T2_2["Thought: 10+13=23 (Left: 13, 23)"]

T2_1 --> Eval2_1["Eval: Likely"]
T2_2 --> Eval2_2["Eval: Impossible"]

Eval2_1 --> Step3_Gen["Step 3: Final Step"]
Step3_Gen --> Final["Last Thought: 3*? -> 24?"]

style Input fill:#ffe0b2
style Stop fill:#ffcdd2
style Step3_Gen fill:#c8e6c9

4.2 창의적 글쓰기 (Creative Writing): 제약 조건 하의 일관성 유지

과제 개요: 무작위로 주어진 4개의 문장(예: “우주에서 스테이크 냄새가 났다”, “그녀는 수화를 사용했다” 등)을 모두 포함하여 논리적으로 연결된 단락을 작성하는 과제이다.10

ToT 적용 과정:

1. 생성 (Plan): 바로 글을 쓰는 것이 아니라, 글의 전개 계획(Plan)을 먼저 5개 생성한다.

• Prompt: “Generate a one-line plan on how you would write the passage.”.10

2. 평가 (Vote): 5개의 계획을 모델에게 다시 제시하고, 가장 일관성 있고 흥미로운 계획에 투표하도록 한다.
3. 작성: 선정된 최적의 계획을 바탕으로 실제 텍스트를 생성한다.

결과: ToT로 생성된 글은 ’일관성 점수(Coherency Score)’에서 IO나 CoT 방식보다 월등히 높은 평가를 받았다.2 이는 인간 작가가 개요를 짜고 글을 쓰는 방식과 유사하며, LLM이 ’계획’과 ’집행’을 분리했을 때 훨씬 더 고품질의 결과물을 낼 수 있음을 시사한다.

graph TD
Input["Input: 4 Random Sentences"] --> Phase1["Phase 1: Generate Plans"]

Phase1 --> Plan1["Plan A: Focus on Mystery"]
Phase1 --> Plan2["Plan B: Focus on Comedy"]
Phase1 --> Plan3["Plan C: Focus on Drama"]
Phase1 --> Plan4["Plan D: ..."]
Phase1 --> Plan5["Plan E: ..."]

Plan1 --> Vote["Phase 2: Voting (Best Plan)"]
Plan2 --> Vote
Plan3 --> Vote
Plan4 --> Vote
Plan5 --> Vote

Vote --> Select["Selected: Plan B (Most Coherent)"]

Select --> Phase3["Phase 3: Write Passage"]
Phase3 --> Final["Final Output: Coherent Story"]

style Input fill:#e1bee7,stroke:#4a148c
style Select fill:#ce93d8,stroke:#4a148c
style Final fill:#f3e5f5,stroke:#4a148c

4.3 미니 크로스워드 (Mini Crosswords): 고난도 제약 충족 문제

과제 개요: 5x5 격자의 크로스워드 퍼즐을 푼다. 가로, 세로 단어의 철자가 정확히 일치해야 하며, 힌트에 맞는 단어를 찾아야 한다.

ToT 적용 과정:

1. 탐색 (DFS): 단어 하나를 채우는 것을 하나의 단계(Step)로 본다.
2. 평가 (Pruning): 현재 채워진 단어들이 유효한지, 그리고 남은 빈칸을 채울 수 있는지 평가한다.

• 만약 가로 1번 단어를 채웠는데, 그로 인해 세로 1번 단어 자리에 존재하지 않는 철자 조합이 생긴다면, 즉시 **백트래킹(Backtracking)**하여 가로 1번 단어를 다른 것으로 교체한다.

3. 결과: GPT-4 + CoT의 단어 레벨 성공률은 약 15% 미만이었으나, ToT는 **단어 성공률 60%, 글자 정확도 78%**를 달성했다.15 일부 연구에서는 CoT의 성공률이 1% 수준으로 보고되기도 하여, ToT와의 격차가 가장 극명하게 드러난 과제이다.10

graph TD

subgraph "DFS: Crosswords / Constrained Logic"
DFS_Root["Root State"]
DFS_Path1["Step 1"]
DFS_Path2["Step 2"]
DFS_Err["Error Detected"]

DFS_Root --> DFS_Path1
DFS_Path1 --> DFS_Path2
DFS_Path2 --> DFS_Err
DFS_Err --"Backtrack"--> DFS_Path1
DFS_Path1 --"New Path"--> DFS_Path2_New["Step 2 (Corrected)"]

style DFS_Root fill:#b2dfdb
style DFS_Err fill:#ffcdd2
end

subgraph "BFS: Creative Writing / Game of 24"
BFS_Root["Root State"]
BFS_L1_1["State 1"]
BFS_L1_2["State 2"]
BFS_L1_3["State 3"]

BFS_Root --> BFS_L1_1
BFS_Root --> BFS_L1_2
BFS_Root --> BFS_L1_3

BFS_L1_1 --"Keep top b"--> BFS_L2_1["Next State A"]
BFS_L1_2 --"Discarded"--> X1["Pruned"]
BFS_L1_3 --"Keep top b"--> BFS_L2_2["Next State B"]

style BFS_Root fill:#e1bee7
end

graph TD
Start["Start: 5x5 Empty Grid"] --> Step1["Step 1: Fill 1-Across"]

Step1 --> OptA["Option A: 'WITCH'"]
Step1 --> OptB["Option B: 'APPLE'"]

OptA --> Check1["Check: Vertical Constraints"]
OptB --> Check1

Check1 --"1-Down Impossible with 'W'"--> PruneA["Prune Option A"]
Check1 --"1-Down Possible with 'A'"--> KeepB["Keep Option B"]

KeepB --> Step2["Step 2: Fill 1-Down"]
Step2 --> OptC["Option C: 'ADORE'"]

OptC --> Check2["Check: Remaining Constraints"]

Check2 --"Conflict Detected"--> Backtrack["Backtrack to Step 1"]
Check2 --"Valid"--> Step3["Continue to Step 3"]

style PruneA fill:#ffcdd2,stroke:#c62828
style Backtrack fill:#ffcdd2,stroke:#c62828
style Step3 fill:#c8e6c9,stroke:#2e7d32

5. 비교 분석: 왜 ToT가 더 강력한가?

ToT의 우수성을 명확히 하기 위해 다른 주요 프롬프팅 기법들과 다각도로 비교 분석한다.

graph TD
subgraph "Tree Approach (ToT)"
ToT_Start["Start"] --> ToT_Branch["Branching"]
ToT_Branch --> ToT_Err["Error Branch"]
ToT_Err --"Self-Evaluation"--> ToT_Prune["Prune & Backtrack"]
ToT_Prune --> ToT_Branch
ToT_Branch --> ToT_Correct["Correct Branch"]
ToT_Correct --> ToT_Success["Success"]
style ToT_Success fill:#c8e6c9
end

subgraph "Linear Approach (CoT)"
CoT_Start["Start"] --> CoT_Err["Error occurs"]
CoT_Err --> CoT_Prop["Error Propagation"]
CoT_Prop --> CoT_Fail["Wrong Answer (Cannot Recover)"]
style CoT_Fail fill:#ffcdd2
end

5.1 ToT vs. Chain of Thought (CoT)

CoT는 흐르는 물과 같아서 한 번 방향이 잡히면 되돌릴 수 없다. 반면 ToT는 지도를 펴놓고 목적지를 찾아가는 과정과 같다. 막힌 길을 미리 확인하고 피해 갈 수 있는 능력이 핵심적인 차이이다.4

5.2 ToT vs. Self-Consistency

Self-Consistency는 여러 번 시도하여 다수결을 따르는 전략이다. 이는 확률적으로 정답을 맞힐 가능성을 높여주지만, 문제 해결 과정의 효율성을 개선하지는 않는다. 만약 문제 자체가 매우 어려워서 대부분의 경로가 오답으로 이어진다면, Self-Consistency 역시 오답을 ’확신’하게 된다. 반면 ToT는 중간 단계마다 평가를 수행하므로, 오답으로 가는 경로를 조기에 차단하고 자원을 유망한 경로에 집중할 수 있다.5

5.3 비용 및 효율성 분석

ToT의 가장 큰 단점은 비용이다.

• 토큰 사용량: 트리 구조를 생성하고 각 노드를 평가해야 하므로, 단일 CoT 대비 수십 배에서 수백 배의 토큰이 소모될 수 있다.8
• 지연 시간 (Latency): 여러 번의 LLM 호출과 평가 과정이 필요하므로 실시간 응답이 필요한 챗봇 서비스 등에는 적용하기 어렵다.7
• 구현 복잡도: 단순히 프롬프트만 입력하는 것이 아니라, 트리를 관리하고 탐색하는 외부 스크립트(Python 등)나 매우 정교한 프롬프트 체인이 필요하다.12

6. 심층 통찰: ToT가 AI 연구에 던지는 함의

ToT는 단순한 성능 향상 도구를 넘어, 인공지능이 인간의 사고 방식을 닮아가는 과정에서 중요한 이정표를 제시한다.

6.1 메타인지(Metacognition)의 구현

ToT의 ‘상태 평가(State Evaluation)’ 과정은 AI가 자신의 출력물을 객관화하여 바라보는 메타인지의 초기 형태라고 볼 수 있다.8 “내가 지금 생각한 것이 맞는가?”, “이 방향으로 가면 답이 나올까?“라고 스스로 자문하는 과정은, 기존의 생성형 AI가 가진 ‘환각(Hallucination)’ 문제를 완화하는 데에도 기여할 수 있다. 자신이 모르는 것을 모른다고 하거나, 불가능한 경로를 불가능하다고 판단하는 능력이 향상되기 때문이다.

6.2 신경-상징적 AI (Neuro-Symbolic AI)로의 가교

전통적인 AI(GOFAI - Good Old-Fashioned AI)는 탐색과 논리에 강했지만 유연성이 부족했다. 딥러닝 기반의 LLM은 유연성과 패턴 인식에 강하지만 논리적 엄밀성이 부족했다. ToT는 LLM(신경망)을 통해 직관적인 후보를 생성하고, 트리 탐색(상징적 알고리즘)을 통해 논리적 구조를 잡아주는 형태로, 두 패러다임의 장점을 결합한 실용적인 신경-상징적 AI 모델로 해석될 수 있다.4

graph TD
subgraph "Neuro-Symbolic Integration"
LLM["Neural Network (LLM)"]
Algo["Symbolic Algorithm (Search)"]

LLM --"1: Intuition & Generation"--> Thoughts["Candidate Thoughts"]
Algo --"2: Structure & Control"--> Tree["Tree Topology"]

Thoughts --> Tree
Tree --"3: Query for Evaluation"--> LLM
LLM --"4: Value/Feedback"--> Algo

Algo --"5: Navigation Decision"--> NextStep["Next Prompt"]
NextStep --> LLM
end

style LLM fill:#e3f2fd,stroke:#2196f3
style Algo fill:#fff9c4,stroke:#fbc02d

6.3 미래 전망: Graph of Thoughts (GoT)와 그 너머

ToT는 트리 구조에 국한되어 있지만, 실제 인간의 사고는 훨씬 더 복잡한 네트워크 구조를 띤다. 여러 아이디어가 합쳐지기도 하고(Aggregation), 과거의 생각으로 다시 돌아와 순환하기도(Recurrence) 한다. 이러한 구조를 반영하여 ToT를 확장한 Graph of Thoughts (GoT) 연구가 이미 진행되고 있다.3 GoT는 생각들 간의 더욱 복잡한 상호작용을 모델링하여, 요약, 코딩, 논문 작성 등 더욱 복잡한 과제에서 효율성을 극대화할 것으로 기대된다.

또한, ToT의 높은 비용 문제를 해결하기 위해, ToT로 생성된 고품질의 ’사고 과정 데이터’를 사용하여 작은 모델을 미세 조정(Fine-tuning)하거나 강화학습(RL)시키는 연구도 유망하다.6 즉, 훈련 단계에서는 ToT와 같은 ‘시스템 2’ 사고를 통해 깊이 있게 학습하고, 추론 단계에서는 이를 내재화하여 빠르고 효율적으로 답을 내놓는 모델을 만드는 것이다.

graph TD

subgraph "Graph of Thoughts (Network)"
G1["Thought A"] --> G2["Thought B1"]
G1 --> G3["Thought B2"]
G2 --> G4["Thought C (Aggregation)"]
G3 --> G4
G4 --> G5["Thought D"]
G5 --"Recurrence/Loop"--> G1
end

subgraph "Tree of Thoughts (Branching)"
T1["Thought A"] --> T2["Thought B1"]
T1 --> T3["Thought B2"]
T2 --> T4["Thought C1"]
T3 --> T5["Thought C2"]
end

subgraph "Chain of Thought (Linear)"
C1["Thought A"] --> C2["Thought B"]
C2 --> C3["Thought C"]
end

style C1 fill:#f5f5f5,stroke:#bdbdbd
style T1 fill:#e1f5fe,stroke:#0277bd
style G1 fill:#e0f2f1,stroke:#00695c
style G4 fill:#b2dfdb,stroke:#004d40,stroke-width:2px

7. 결론

사고의 나무(Tree of Thoughts)는 거대 언어 모델이 직면한 추론의 한계를 구조적인 ’탐색’과 ’평가’의 도입을 통해 극복하고자 하는 혁신적인 프레임워크이다. 실험 결과는 수학, 창의적 글쓰기, 퍼즐 등 계획 능력이 필수적인 영역에서 ToT가 기존 방식에 비해 압도적인 성능을 발휘함을 증명했다. 비록 높은 연산 비용과 구현의 복잡성이라는 현실적인 장벽이 존재하지만, ToT가 제시한 ’생각의 구조화’와 ’자기 평가’라는 방향성은 향후 인공지능이 인간 수준의 범용 문제 해결 능력(AGI)에 도달하기 위해 반드시 거쳐야 할 관문임이 분명하다.

우리는 이제 LLM에게 단순히 “답을 말해줘“라고 묻는 시대를 지나, “어떻게 생각해야 할지 계획을 세우고, 그 계획을 검증하며 최적의 답을 찾아가라“고 요구하는 시대로 진입하고 있다. ToT는 바로 그 새로운 시대의 서막을 여는 핵심적인 열쇠이다.

8. 참고 자료

1. [PDF] Tree of Thoughts: Deliberate Problem Solving with Large Language Models, https://www.semanticscholar.org/paper/Tree-of-Thoughts%3A-Deliberate-Problem-Solving-with-Yao-Yu/2f3822eb380b5e753a6d579f31dfc3ec4c4a0820
2. Tree of Thoughts: Deliberate Problem Solving with Large Language Models - arXiv, https://arxiv.org/pdf/2305.10601
3. Demystifying Chains, Trees, and Graphs of Thoughts - arXiv, https://arxiv.org/html/2401.14295v3
4. Understanding and Implementing the Tree of Thoughts Paradigm - Hugging Face, https://huggingface.co/blog/sadhaklal/tree-of-thoughts
5. AI Prompting (2/10): Chain-of-Thought Prompting—4 Methods for Better Reasoning - Reddit, https://www.reddit.com/r/PromptSynergy/comments/1if2882/ai_prompting_210_chainofthought_prompting4/
6. Advanced Prompt Engineering — Self-Consistency, Tree-of-Thoughts, RAG | by Sulbha Jain, https://medium.com/@sulbha.jindal/advanced-prompt-engineering-self-consistency-tree-of-thoughts-rag-17a2d2c8fb79
7. 8 Chain-of-Thought Techniques To Fix Your AI Reasoning | Galileo, https://galileo.ai/blog/chain-of-thought-prompting-techniques
8. Rethinking Thinking Tokens: LLMs as Improvement Operators - arXiv, https://arxiv.org/html/2510.01123v1
9. What is Tree Of Thoughts Prompting? - IBM, https://www.ibm.com/think/topics/tree-of-thoughts
10. Tree of Thoughts (ToT): Enhancing Problem-Solving in LLMs - Learn Prompting, https://learnprompting.org/docs/advanced/decomposition/tree_of_thoughts
11. Unraveling the “Tree of Thoughts” — A New Frontier in Language Model Prompting Techniques | by Vikram Singh Chauhan | Medium, https://medium.com/@vikram40441/unraveling-the-tree-of-thoughts-a-new-frontier-in-language-model-prompting-techniques-ff19dbc2b935
12. Tree of Thoughts. “Tree of Thoughts” (ToT) is a new… | by Bill Moore | Medium, https://medium.com/@billmoore_92080/tree-of-thought-ae340068eef8
13. Beginner’s Guide To Tree Of Thoughts Prompting (With Examples) | Zero To Mastery, https://zerotomastery.io/blog/tree-of-thought-prompting/
14. Tree of Thoughts (ToT) - Prompt Engineering Guide, https://www.promptingguide.ai/techniques/tot
15. Tree of Uncertain Thoughts Reasoning for Large Language Models, https://www.alphaxiv.org/overview/2309.07694v1
16. Optimizing Large Language Models to Solve Crossword Puzzles - Stanford University, https://web.stanford.edu/class/cs224n/final-reports/256725260.pdf
17. Chain of Thought Prompting: A Deep Dive into the AI Architecture Pattern - Rahul Krishnan, https://solutionsarchitecture.medium.com/chain-of-thought-prompting-a-deep-dive-into-the-ai-architecture-pattern-d35cd8b52c53
18. Chain of Thought Prompting (CoT): Everything you need to know - Vellum AI, https://www.vellum.ai/blog/chain-of-thought-prompting-cot-everything-you-need-to-know
19. Chain-of-thought, tree-of-thought, and graph-of-thought: Prompting techniques explained, https://wandb.ai/sauravmaheshkar/prompting-techniques/reports/Chain-of-thought-tree-of-thought-and-graph-of-thought-Prompting-techniques-explained—Vmlldzo4MzQwNjMx
20. Towards Large Reasoning Models: A Survey of Reinforced Reasoning with Large Language Models - arXiv, https://arxiv.org/html/2501.09686v1
21. Tree of Thoughts: Deliberate Problem Solving with Large Language Models - OpenReview, https://openreview.net/forum?id=5Xc1ecxO1h